//
// Created by liushuai on 2021/1/16.
//

#include <iostream>
#include "longestPalindromeSubseq.h"
int longestPalindromeSubseq(std::string& s){
    int num_size = s.size();
    std::vector<int> col(s.size(),0);
    std::vector<std::vector<int>> dp(s.size(),col);
    for(int start=num_size-1;start>=0;start--){
        for(int end=start;end<num_size;end++){
            if(start==end)
                dp[start][end] = 1;
            else{
                if(s[start]==s[end])
                    dp[start][end] = dp[start+1][end-1]+2;
                else
                    dp[start][end] = std::max(dp[start][end-1],dp[start+1][end]);
            }

        }
    }
    return dp[0][num_size-1];
}